//有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。 
//
// 
//
// 给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 10⁹ + 7 取模 的值。 
//
// 平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: n = 3
//输出: 5
//解释: 五种不同的方法如上所示。
// 
//
// 示例 2: 
//
// 
//输入: n = 1
//输出: 1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 1000 
// 
//
// Related Topics 动态规划 👍 332 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-10-07 15:11:00
 * @description 790.多米诺和托米诺平铺
 */
public class DominoAndTrominoTiling{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new DominoAndTrominoTiling().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*实际上可以把方块转化为三种，一二三格宽的*/
		 private static final long MOD = (long) 1e9 + 7;

	public int numTilings(int n) {
		if (n == 1) return 1;
		long[] f = new long[n + 1];
		f[0] = f[1] = 1;
		f[2] = 2;
		for (int i = 3; i <= n; ++i)
			f[i] = (f[i - 1] * 2 + f[i - 3]) % MOD;
		return (int) f[n];
	}
	/*空间优化*/
	public int numTilings1(int n) {
		if (n == 1) return 1;
		long a = 1, b = 1, c = 2;
		for (int i = 3; i <= n; ++i) {
			long f = (c * 2 + a) % MOD;
			a = b;
			b = c;
			c = f;
		}
		return (int) c;
	}

/*定义四种状态，上下都被覆盖3，上被覆盖1，下被覆盖2，上下都没覆盖0，*/
	public int numTilings2(int n) {
		int [][]dp=new int[n+1][3];
		dp[0][3]=1;
		for (int i = 1; i <=n ; i++) {
			dp[i][0]=dp[i-1][3];
			dp[i][1]= (int) ((dp[i-1][0]+dp[i-1][2])%MOD);
			dp[i][2]=(int) ((dp[i-1][0]+dp[i-1][1])%MOD);
			dp[i][3]= (int) ((((dp[i - 1][0] + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD);
		}
		return dp[n][3];
	}
/*矩阵快速幂*/
	public int numTilings3(int n) {
		return 1;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
